The present invention relates to error correction circuits for detecting and correcting errors in transmitted or stored digital data and in particular to an error correction circuit providing high-speed linear programming detection and error correction.
The reliable transmission and storage of digital data, for example binary symbols transmitted as electrical impulses over data communication networks or stored on digital storage media, may employ error detection and/or correction circuitry and protocols to guard the transmitted or stored data against corruption.
Generally, error detection and correction is obtained by providing redundant bits in the transmitted or stored data. A naïve redundancy scheme may simply duplicate the transmission or storage of the data; however, sophisticated redundancy systems provide a limited number of detection and correction bits (henceforth “check bits”) each of which serve to detect and/or correct errors in multiple other data bits. For example, an 8-bit message might have a single ninth check bit termed a parity bit. This parity bit is set or reset so as to make the total number of set bits in the message and parity bit an even number. It will be understood that corruption of any one of the message or parity bits caused by a crossover (i.e. changing of the bits during transmission or during storage) will be readily detected by checking whether the total number of bits set is even. If not, an error in transmission or storage can be assumed.
More generally, multiple check bits can be added to any stored or transmitted data word allowing both detection and correction of errors in the message bits. These extra bits increase the numeric spacing or Hamming distance between legitimate message symbols represented by the data and check bits taken together. Errors are detected if the received symbol is positioned between legitimate symbols and error correction is obtained by choosing the closest legitimate symbol. In this respect it will be understood that error correction simply chooses the most likely correct symbol.
Sophisticated error detection and correction systems may employ “low density parity check codes” in which overlapping subsets of data bits and check bits are subject to independent constraints (e.g. even parity), the constraints thus each applying to only a small subset of the bits. Low-density parity check codes allow transmission of data very close to the Shannon limit that relates the amount of information that can be transmitted over a channel of a given bandwidth in the presence of given noise interference.
Decoding information that has been encoded using low density parity check codes is computationally demanding, involving the determination of a most likely transmitted string in the face of errors and subject to the overlapping constraints of the originally transmitted message. One method of performing this decoding, termed “belief propagation”, iteratively communicates values of the received bits in each subset (as maintained in a buffer) to a circuit that applies attempts to reconcile the received values according to their constraint parity and retransmit updated reconciled values to the buffer. Each bit of the buffer receives updates from multiple reconciling circuits and a mechanism is provided to integrate the different and often conflicting updates. This cycle is performed iteratively.
Belief propagation is parallelizable to the extent that the calculations associated with each reconciliation step and each integration step may be implemented simultaneously and independently by separate computing elements. This is important for high-speed message processing.
Unfortunately, although belief propagation is often empirically successful, there is no guarantee that it will converge to a set of bits that meets the constraint of the parity rules. Further, belief propagation is subject to an “error floor” representing a limit to its ability to detect and correct errors.